系数|多样性_基向量非基向量基解（基本解）可行解基本可行解最优解

篇首语：本文由编程笔记#小编为大家整理，主要介绍了基向量非基向量基解（基本解）可行解基本可行解最优解相关的知识，希望对你有一定的参考价值。

昨天查了不能说一晚上吧&＃xff0c;也差不多&＃xff0c;不知道是问题太简单了还是没有多少能说清楚的&＃xff0c;但至少网上的回答令我大失所望&＃xff0c;让我云里雾里的&＃xff0c;完全迷惑了这些名词到底是个啥&＃xff0c;如何清楚的理解它们。

幸好之前搞了一本清华大学出版社出版的《运筹学基础》&＃xff0c;晚上泡脚的时候终于搞明白了这些概念。为让跟我一样困惑的初学者们能清楚的理解它们的含义&＃xff0c;故此记录。

文章目录

• • • • 可行解
      • 基向量和非基向量
      • 基变量、非基变量、基解
      • 基本可行解
      • 图解
      
      
    
    
  
  

可行解

凡是满足约束条件&＃xff08;2&＃xff09;和&＃xff08;3&＃xff09;的解




x


&＃61;



[







x


1










x


2









⋮












x


n







]




\\bf x&＃61;\\begin bmatrix x_1 \\\\x_2 \\\\ \\vdots\\\\ x_n\\end bmatrix


x&＃61;⎣⎢⎢⎢⎡​x1​x2​⋮xn​​⎦⎥⎥⎥⎤​称为线性规划问题的可行解&＃xff0c;同时满足目标函数&＃xff08;1&＃xff09;的可行解成为最优解。

基向量和非基向量

设线性规划约束方程组中的系数矩阵$\mathbf{A}$的秩为$m(n>m)$,则$\mathbf{A}$中任一个$\mathbf{m}$阶可逆矩阵$\mathbf{B}$ 称为线性规划问题的一个基矩阵&＃xff0c;简称基。记




B


&＃61;


(



p


1



,



p


2



,


⋯
 

,



p


m



)



\\bf B&＃61;( p_1, p_2,\\cdots,p_m)


B&＃61;(p1​,p2​,⋯,pm​)&＃xff0c;则称





p


j



(


j


&＃61;


1


,


2


,


⋯
 

,


m


)



p_j(j&＃61;1,2,\\cdots,m)


pj​(j&＃61;1,2,⋯,m) 为$\mathbf{B}$的一个基向量&＃xff0c;而$\mathbf{A}$ 中剩余$n-m$个列向量称为非基向量。

何为任一&＃xff1f;
也就是说 $\mathbf{B}$ 是矩阵 $\mathbf{A}$ 中任一m列组成的矩阵&＃xff0c;那么$\mathbf{B}$ 可以表示为&＃xff08;假设矩阵$\mathbf{A}$有四列&＃xff0c;$r\&＃61;2$&＃xff09;&＃xff1a;





B


&＃61;


(



p


1



,



p


2



)


o


r


B


&＃61;


(



p


1



,



p


3



)


o


r


B


&＃61;


(



p


1



,



p


4



)


o


r


B


&＃61;


(



p


2



,



p


3



)


o


r


B


&＃61;


(



p


2



,



p


4



)


o


r


B


&＃61;


(



p


3



,



p


4



)



\\bf B&＃61;(p_1,p_2) or B&＃61;(p_1,p_3) or B&＃61;(p_1,p_4) or B&＃61;(p_2,p_3) or B&＃61;(p_2,p_4) or B&＃61;(p_3,p_4)


B&＃61;(p1​,p2​)orB&＃61;(p1​,p3​)orB&＃61;(p1​,p4​)orB&＃61;(p2​,p3​)orB&＃61;(p2​,p4​)orB&＃61;(p3​,p4​) , 只要$\mathbf{B}$可逆&＃xff0c;即$|\mathbf{B}|/\&＃61;0$, 则就有基本解&＃xff0c;也就是后边提到的线性规划最多有基本解的个数为




C




n


m




C^m_n


Cnm​

基变量、非基变量、基解

取$\mathbf{A}$中一个基




B


&＃61;


(



p


1



,



p


2



,


⋯
 

,



p


m



)



\\bf B&＃61;(p_1,p_2,\\cdots,p_m)


B&＃61;(p1​,p2​,⋯,pm​) , 对应的基变量为





x


1



,



x


2



,


⋯
 

,



x


m




\\bf x_1,x_2,\\cdots,x_m


x1​,x2​,⋯,xm​, 则





x



m


&＃43;


1




,



x



m


&＃43;


2




,


⋯
 

,



x


n




\\bf x_m&＃43;1,x_m&＃43;2,\\cdots,x_n


xm&＃43;1​,xm&＃43;2​,⋯,xn​ 为非基变量&＃xff0c;当非基变量取值均为零时且满足约束&＃xff08;2&＃xff09;的一个解$x$ 称为关于基$\mathbf{B}$的一个基本解&＃xff0c;线性规划问题最多只有




C




n


m




C^m_n


Cnm​个基本解

基本可行解

若一个基本解$x$同时满足非负约束条件&＃xff08;3&＃xff09;&＃xff0c;则称$x$为基本可行解。

图解

其实&＃xff0c;这些概念的大小关系可以通过一张图完美的解释&＃xff0c;上图

从图中我们可以得出这样的一些结论&＃xff08;自己理解&＃xff09;&＃xff1a;

1. 可行解或者基本解是针对约束而言的&＃xff0c;最优解是针对约束和目标函数而言的&＃xff1b;
2. 基本可行解是可行解的一个特解&＃xff1b;
3. 基本解中存在非可行性解&＃xff0c;换句话说非可行解最多只满足约束中的一个&＃xff0c;而不能同时满足两个约束&＃xff0c;也存在非可行解满足目标函数&＃xff0c;但不完全满足约束的情况

第三条或许就是为什么很多多目标EA对比分析feasible solutions 和infeasible solutions的原因了。但在例如NSGA中 infeasible solution与feasible solution是在constraint中提到的&＃xff0c;感觉是为了保证多样性&＃xff0c;即使两个均为infeasible solution&＃xff0c;还是选择了smaller constraint violation的那个解&＃xff0c;让其拥有better Pareto Rank。

疑问&＃xff1a;是不是所谓的最优解中存在infeasible solutions呢&＃xff1f;&＃xff08;&＃x1f436;&＃xff09;